import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Dijkstras {

	/**
	 * Performs Dijskstra's Algorithm on the given graph, finding shortest paths
	 * to all vertices from a given vertex.
	 * 
	 * @param graph The graph to find shortest paths on.
	 * @param init The vertex from which to find shortest paths, must be in
	 *            Graph.
	 * @return A map from a vertex name to the shortest path node.
	 * @throws IllegalArgumentException if the given vertex is not in the graph.
	 */
	public static Map<String, DijkstrasNode> dijsktras(SimpleGraph graph,
			String init) {
		Map<String, DijkstrasNode> results = new HashMap<String, DijkstrasNode>();
		BinaryHeap heap = new BinaryHeap();
		Iterator iter = graph.vertices();
		Vertex iterVert;
		DijkstrasNode thisNode;
		DijkstrasNode farNode;
		Edge edge;
		boolean vertInGraph = false;
		// add nodes to heap and map
		while (iter.hasNext()) {
			iterVert = (Vertex) iter.next();
			thisNode = new DijkstrasNode();
			thisNode.setCurrentVertex(iterVert);
			thisNode.setPreviousVertex(null);
			thisNode.setKnown(false);
			if (iterVert.getName().equals(init)) {
				// this is the initial vertex
				thisNode.setLabel(0);
				vertInGraph = true;
			} else {
				thisNode.setLabel(Integer.MAX_VALUE);
			}
			heap.insert(thisNode);
			results.put(iterVert.getName().toString(), thisNode);
		}

		// Stop now if we never found the init vertex
		if (!vertInGraph) {
			throw new IllegalArgumentException("Given vertex " + init
					+ " not found in graph");
		}

		// Iterate over all vertices
		while (!heap.isEmpty()) {
			try {
				thisNode = (DijkstrasNode) heap.deleteMin();
			} catch (EmptyHeapException e) {
				throw new IllegalStateException("Horrific failure of BinHeap");
			}
			thisNode.setKnown(true);
			iter = graph.incidentEdges(thisNode.getCurrentVertex());
			// Iterate over edges adjacent to this vertex.
			while (iter.hasNext()) {
				edge = (Edge) iter.next();
				iterVert = graph.opposite(thisNode.getCurrentVertex(), edge);
				farNode = results.get(iterVert.getName());
				// Compare the value of the opposite side of the edge, if
				// other node is not known.
				if (!farNode.isKnown()
						&& thisNode.getLabel() + ((Double) edge.getData()).intValue()
							< farNode.getLabel()) {
					// This path is better, record it.
					farNode.setLabel(thisNode.getLabel()
							+ ((Double) edge.getData()).intValue());
					farNode.setPreviousVertex(thisNode.getCurrentVertex());
					// Fix the heap.
					heap.percolateUp(farNode.getHeapLocation());
				}
			}
		}
		return results;
	}

	/**
	 * Prints the shortest path between two vertices using map generated from
	 * running dijkstra's.
	 **/
	public static String getPathString(Map<String, DijkstrasNode> map,
			String fromvert) {
		StringBuilder sb = new StringBuilder();
		DijkstrasNode node = map.get(fromvert);
		if (node == null) {
			throw new IllegalArgumentException("Given vertex " + fromvert
					+ " not found in graph");
		}
		sb.append("[" + node.getCurrentVertex().getName());
		while (node.getPreviousVertex() != null) {
			node = map.get(node.getPreviousVertex().getName());
			sb.append(" -> " + node.getCurrentVertex().getName());
		}
		sb.append("]");
		return sb.toString();
	}

	/** Runs simple UI to read from Graph files **/
	public static void main(String args[]) {
		// Load graph file
		SimpleGraph graph = new SimpleGraph();
		try {
			GraphInput.LoadSimpleGraph(graph);
		} catch (Error e) {
			System.out.println("Unable to read that file as a graph.");
			return;
		}

		// Loop input until user quits
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));
		String invert = "";
		String outvert = "";
		String pathstring = "";
		Map<String, DijkstrasNode> results = null;
		while (true) {
			while (invert.equals("") || outvert.equals("")) {
				try {
					System.out.print("Please input start vertex (or \"quit\"): ");
					invert = reader.readLine();
					System.out.print("Please input end vertex (or \"quit\"): ");
					outvert = reader.readLine();
				} catch (IOException e) {
					System.out.println("Unable to read input, try again");
				}
			}
			if (invert.equals("quit") || outvert.equals("quit")) {
				return;
			}
			try {
				results = dijsktras(graph, outvert);
				pathstring = getPathString(results, invert);
			} catch (IllegalArgumentException e) {
				// Invalid vertex given.
				System.out.println(e.getMessage());
				invert = "";
				outvert = "";
				continue;
			}
			System.out.println(String.format(
					"Shortest path from %s to %s is %s", invert, outvert,
					pathstring));
			System.out.println(String.format("Total path weight: %d", results
					.get(invert).getLabel()));
			invert = "";
			outvert = "";
		}
	}
}
